#ifndef DATA_STRUCTURE_SORTTOOL_H
#define DATA_STRUCTURE_SORTTOOL_H

#include <iostream>
#include <cstring>
#include "vector"

using namespace std;

void swap(int *a, int *b) {
    if (a != b) {
        *a = *a + *b;
        *b = *a - *b;
        *a = *a - *b;
    }
}

int PartSort(vector<int> &a, int left, int right, int &compareNum, int &moveNum) {
    int key = left;
    while (left < right) {
        while (left < right && a[right] >= a[key]) {
            right--;
            compareNum++;
        }
        while (left < right && a[left] <= a[key]) {
            left++;
            compareNum++;
        }
        swap(&a[left], &a[right]);
        moveNum += 3;
    }
    swap(&a[key], &a[left]);
    moveNum += 3;
    return left;
}

void QuickSort(vector<int> &a, int left, int right, int &compareNum, int &moveNum) {
    if (left >= right) return;
    int key = PartSort(a, left, right, compareNum, moveNum);
    QuickSort(a, left, key - 1, compareNum, moveNum);
    QuickSort(a, key + 1, right, compareNum, moveNum);
}

void quickSort(vector<int> &arr, int &compareNum, int &moveNum) {
    QuickSort(arr, 0, arr.size() - 1, compareNum, moveNum);
}


void shell(vector<int> &arr, int &compareNum, int &moveNum) {
    int n = arr.size();
    if (n <= 1) {
        return;
    }
    for (int gap = n / 2; gap >= 1; gap = gap / 2) {//确定希尔排序分组长度
        compareNum++;
        for (int i = 0; i < gap; i++) {//对于每个分组
            compareNum++;
            for (int j = i + gap; j < n; j += gap) {//组内插入排序
                compareNum++;
                int k = j - gap;
                int tmp = arr[j];
                while (k >= i && arr[k] > tmp) {
                    compareNum++;
                    moveNum++;
                    arr[k + gap] = arr[k];
                    k -= gap;
                }
                moveNum++;
                arr[k + gap] = tmp;
            }
        }
    }
}


void printArr(vector<int> &arr) {
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

#endif //DATA_STRUCTURE_SORTTOOL_H
